//方法：栈实现

//复杂版
typedef char STDateType;

typedef struct Stack {
	STDateType* a;
	int top;
	int capacity;
}ST;

void Stack_Init(ST* ps) {
	ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
	if (ps->a == NULL) {
		printf("Malloc fail.\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = -1;
}
void Stack_Destory(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = -1;
}

void Stack_Push(ST* ps, STDateType x) {
	assert(ps);
	if (ps->top == ps->capacity - 1) {
		STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
		if (tmp == NULL) {
			printf("Realloc fail.\n");
			exit(-1);
		}
		else {
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->top++;
	ps->a[ps->top] = x;
}

void Stack_Pop(ST* ps) {
	assert(ps);
	assert(ps->top > -1);
	ps->top--;
}

STDateType Stack_Top(ST* ps) {
	assert(ps);
	assert(ps->top > -1);
	return ps->a[ps->top];
}

bool Stack_Empty(ST* ps) {
	assert(ps);
	return ps->top == -1;
}
bool isValid(char* s) {
    ST st;
    Stack_Init(&st);
    while(*s != '\0'){
        switch(*s){
            case '{':case '[':case '(':{
                Stack_Push(&st, *s);
                s++;
                break;
            }
            case '}':case ']':case ')':{
                if(Stack_Empty(&st)){
                    Stack_Destory(&st);
                    return false;
                }else{
                    char top = Stack_Top(&st);
                    Stack_Pop(&st);
                    if((*s == '}' && top != '{') || (*s == ']' && top != '[') || (*s == ')' && top != '(')){
                        Stack_Destory(&st);
                        return false;
                    }else{
                        s++;
                    }
                    break;
                }
            }
        }
    }
    if(!Stack_Empty(&st)){
        Stack_Destory(&st);
        return false;
    }
    Stack_Destory(&st);
    return true;
}

//精简版(大佬写法）
bool isValid(char* s) {
    char mp[128] = {};
    mp[')'] = '(';
    mp[']'] = '[';
    mp['}'] = '{';

    int top = 0; // 直接把 s 当作栈
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (mp[c] == 0) { // c 是左括号
            s[top++] = c; // 入栈
        } else if (top == 0 || s[--top] != mp[c]) { // c 是右括号
            return false; // 没有左括号，或者左括号类型不对
        }
    }
    return top == 0; // 所有左括号必须匹配完毕
}

/*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。*/